package com.demo.jzoffer2;

import org.junit.Test;

/**
 * @author gy
 * @date 2023/03
 */
public class Test0313_02 {
    /**
     * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），
     * 每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？
     * 例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
     *
     * 输入: 2
     * 输出: 1
     * 解释: 2 = 1 + 1, 1 × 1 = 1
     *
     * 输入: 10
     * 输出: 36
     * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
     *
     * 2 <= n <= 58
     *
     * 思路分析： 将长度为n的绳子切为a段：
     * n = n1 + n2 +...+ na
     * 本题等价与求解
     * max（n1 * n2 *...* na）
     *
     * 数学推论：具体推解过程 见题解
     * 1.当所有绳段长度相等时，乘积最大
     * 2.最优的绳段长度为3
     *
     * 切分规则：
     * 尽可能将绳子切分为长度为3的线段，剩余的绳子长度0，1，2
     * 1.剩余为0，代表刚好全部分为长度为3线段
     * 2.剩余为1，此时 3 * 1 < 2 * 2 这种情况要转换 将最后一段长度为4的线段切分为 2 * 2
     * 3.剩余为2，此时 2 * 1 > 1 * 1 无需再次切分为 1 * 1两段
     *
     * 算法流程：
     * 1.当 n <= 3 时 按道理不应该进行拆分，但是题目要求 拆分的段数 m>1 且 2 <= n <= 58
     * n = 3 拆为 2 和 1   2*1 = 2
     * n = 2 拆为 1 和 1   1*1 = 1
     *
     * 2.当 n> 3 时 n = 3a + b  其中 a为段数 b为余数
     * a = n / 3
     * b = n % 3
     *
     * 3 ^ a  3的 a次方
     *
     * b = 0  3的 a次方
     * b = 1  3的 a-1 次方 * 4
     * b = 2  3的 a 次方 * 2
     *
     * @param n
     * @return
     */
    public int cuttingRope(int n) {
        if (n <= 3){
            return n - 1;
        }
        int a = n / 3;
        int b = n % 3;
        if (b == 0){
            return (int) Math.pow(3, a);
        }
        if (b == 1){
            return (int) (Math.pow(3,a - 1) * 4);
        }
        return (int) (Math.pow(3,a) * 2);
    }


    /**
     * 注意：可以使用动态规划求解
     */
    @Test
    public void m1() {

    }

    @Test
    public void m2() {
    }

}
